#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;


int max_distance(ckt & ptrckt, int dest_row_ID, node & this_node)
{
	tinyRow & dest_row = ptrckt.tinyRows[dest_row_ID];
	int x1 = dest_row.l_end;
	int x2 = dest_row.r_end;
	int y1 = ptrckt.by + (int)(dest_row.y - ptrckt.by) / gridUnit * gridUnit;
	int y2 = y1 + gridUnit;
	int max_x = max(abs(x1 - this_node.initial_x), abs(x2 - this_node.initial_x));
	int max_y = max(abs(y1 - this_node.initial_y), abs(y2 - this_node.initial_y));
	return max_x + max_y + 81;
}

int xy2tinyRowID(ckt & ptrckt, int x, int y)
{
	int rowID = (y - ptrckt.by) / ptrckt.rowHeight * x_gridNum + (x - ptrckt.lx) / gridUnit;
	assert (rowID <= 9 * numBins); 
	return rowID;
}

int rowid2binID(int rowID)
{
	return rowID / (9 * x_gridNum) * x_gridNum + rowID % x_gridNum;
}

void erase_src_node(ckt & ptrckt, tinyRow & src_row, int ID)
{
	vector<int>::iterator position = find(src_row.NodeID.begin(), src_row.NodeID.end(), ID);
	if(position != src_row.NodeID.end())
		src_row.NodeID.erase(position);
}

void tinyRow_setup(ckt & ptrckt) // Set up tinyRows
{
	ptrckt.tinyRows.clear();
	ptrckt.tinyRows.resize(9 * numBins);


	/* TinyRow Initialization */
	for(int i = 0; i < 9 * numBins; i++)
	{
		tinyRow & this_row = ptrckt.tinyRows[i];
		this_row.ID = i;
		this_row.y = (i / x_gridNum) * ptrckt.rowHeight + ptrckt.by;
		// Initialize the bounds of a tinyrow, which may be subject to change due to cell distribution
		this_row.l_end = this_row.lx = ptrckt.lx + (i % x_gridNum) * gridUnit;
		this_row.r_end = this_row.rx = this_row.lx + gridUnit;
		if(this_row.rx > ptrckt.rx)
			this_row.r_end = this_row.rx = ptrckt.rx;
		this_row.isValid = true;
		if(this_row.y > ptrckt.ty - ptrckt.rowHeight)
			this_row.isValid = false;
		
	}


	/* Processing fixed and movable nodes */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{
		if(ptrckt.nodes[i].isNI || ptrckt.nodes[i].shapeIds.size() != 0)
			continue; // Skip TERMINAL_NI and NON-RECTANGULAR NODES

		node & this_node = ptrckt.nodes[i];


		// The range of this node
		int l_col = (this_node.x_coord - ptrckt.lx) / gridUnit;
		int r_col = (this_node.x_coord + this_node.width - ptrckt.lx  - 1) / gridUnit;
		int b_row = (this_node.y_coord - ptrckt.by) / ptrckt.rowHeight;
		int t_row = (this_node.y_coord + this_node.height - ptrckt.by - 1) / ptrckt.rowHeight;

		if(this_node.height == ptrckt.rowHeight) //If this node's height is equal to rowHeight
		{
 			int l_tinyRow_ID = b_row * x_gridNum + l_col;
 			int r_tinyRow_ID = b_row * x_gridNum + r_col;

			if(l_col == r_col) // If this node resides entirely in a tinyRow
			{
 				ptrckt.tinyRows[l_tinyRow_ID].NodeID.push_back(i);
			}
			else if(abs(r_col - l_col) == 1 && this_node.isFixed == false) 
			// If this node is movable and overlaps only two tinyRows
			{
				// Updates the rx of the tinyRow where the left end of the node resides in
				ptrckt.tinyRows[l_tinyRow_ID].rx = this_node.x_coord + this_node.width;
				// Updates the lx of the tinyRow where the right end of the node resides in 
				ptrckt.tinyRows[r_tinyRow_ID].lx = this_node.x_coord + this_node.width;

				ptrckt.tinyRows[l_tinyRow_ID].NodeID.push_back(i);
			}
			else // If this node overlaps more than two tinyRows or is fixed
			{	
				// Updates the rx of the tinyRow where the left end of the node resides in
				ptrckt.tinyRows[l_tinyRow_ID].rx = this_node.x_coord;				
				// Updates the lx of the tinyRow where the right end of the node resides in 
				ptrckt.tinyRows[r_tinyRow_ID].lx = this_node.x_coord + this_node.width;

				// Turn off all the tinyRows in between
				for(int ii = l_tinyRow_ID + 1; ii < r_tinyRow_ID; ii++)
				{
					ptrckt.tinyRows[ii].isValid = false;
				}
			}
		}
		else // If this node overlaps more than one row
		{
			if(l_col == r_col) // If this large cell breaks a column of tinyRows into halves
			{	
				for(int jj = b_row; jj <= t_row; jj++)
				{
					// Turn them off
					ptrckt.tinyRows[jj * x_gridNum + l_col].isValid = false;
				}
			}
			else // The tinyRows on both ends are still usable 
			{	
				for(int jj = b_row; jj <= t_row; jj++)
				{
					// Configure the tinyRows on both ends
					ptrckt.tinyRows[jj * x_gridNum + l_col].rx = this_node.x_coord;
					ptrckt.tinyRows[jj * x_gridNum + r_col].lx = this_node.x_coord + this_node.width;

					// Turn off the tinyRows in between
					for(int kk = l_col + 1; kk < r_col; kk++)
					{
						ptrckt.tinyRows[jj * x_gridNum + kk].isValid = false;
					}
				}
			}
		}
	}

	

	/* Processing non-rectangular fixed shapes */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{	
		for(unsigned m = 0; m < ptrckt.nodes[i].shapeIds.size(); m++) // Skip normal nodes because m = 0
		{    
			// Divide non-regular fixed shapes into rectangles and use tha above method to calculate areas
			unsigned s = ptrckt.nodes[i].shapeIds[m];
			
			int l_col = (ptrckt.shapes[s].x_coord - ptrckt.lx) / gridUnit;
			int r_col = (ptrckt.shapes[s].x_coord + ptrckt.shapes[s].width - ptrckt.lx - 1) / gridUnit;
			int b_row = (ptrckt.shapes[s].y_coord - ptrckt.by) / ptrckt.rowHeight;
			int t_row = (ptrckt.shapes[s].y_coord + ptrckt.shapes[s].height - ptrckt.by - 1) / ptrckt.rowHeight;

			for(int jj = b_row; jj <= t_row; jj++)
			{
				for(int kk = l_col; kk <= r_col; kk++)
				{
					ptrckt.tinyRows[jj * x_gridNum + kk].isValid = false;
				}
			}
		}
	}

	/* Processing row-blockages */
	for(unsigned i = 0; i < ptrckt.blks.size(); i++)
	{
		int l_col = (ptrckt.blks[i].x_coord - ptrckt.lx) / gridUnit;
		int r_col = (ptrckt.blks[i].x_coord + ptrckt.blks[i].width - ptrckt.lx - 1) / gridUnit;
		int b_row = (ptrckt.blks[i].y_coord - ptrckt.by) / ptrckt.rowHeight;
		int t_row = (ptrckt.blks[i].y_coord + ptrckt.blks[i].height - ptrckt.by - 1) / ptrckt.rowHeight;

		for(int jj = b_row; jj <= t_row; jj++)
		{
			for(int kk = l_col; kk <= r_col; kk++)
			{
				ptrckt.tinyRows[jj * x_gridNum + kk].isValid = false;
			}
		}
	}
}


void util_array_setup(ckt & ptrckt, vector<double> & util_array)
{
	/* 0. initialize density map */
	vector<density_bin> bins(numBins);
	for(int j = 0; j < y_gridNum; j++)
		for(int k = 0; k < x_gridNum; k++)
		{
			unsigned binId = j * x_gridNum + k;

			bins[binId].lx = ptrckt.lx + k * gridUnit;
			bins[binId].ly = ptrckt.by + j * gridUnit;
			//bins[binId].hx = bins[binId].lx + gridUnit;
			//bins[binId].hy = bins[binId].ly + gridUnit;
			bins[binId].hx = min(bins[binId].lx + gridUnit, ptrckt.rx);
			bins[binId].hy = min(bins[binId].ly + gridUnit, ptrckt.ty);

			bins[binId].area = max((bins[binId].hx - bins[binId].lx) * (bins[binId].hy - bins[binId].ly), 0);
			bins[binId].m_util = 0.0;
			bins[binId].f_util = 0.0;
			bins[binId].free_space = bins[binId].area;
		}

	/* 1. build density map */
	/* (a) fixed/movable objects */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{
		if(ptrckt.nodes[i].isNI || ptrckt.nodes[i].shapeIds.size() != 0)
			continue;

		int lcol = max((int)floor((ptrckt.nodes[i].x_coord - ptrckt.lx)/gridUnit), 0);
		int rcol = min((int)floor((ptrckt.nodes[i].x_coord + ptrckt.nodes[i].width - ptrckt.lx)/gridUnit), x_gridNum - 1);
		int brow = max((int)floor((ptrckt.nodes[i].y_coord - ptrckt.by)/gridUnit), 0);
		int trow = min((int)floor((ptrckt.nodes[i].y_coord + ptrckt.nodes[i].height - ptrckt.by)/gridUnit), y_gridNum - 1);
		// The left edge of a node resides in the (lcol)_th bin in a row...	

		// For all the overlapped bins of a node
		for(int j = brow; j <= trow; j++)
			for(int k = lcol; k <= rcol; k++)
			{
				unsigned binId= j * x_gridNum+k;

				/* get intersection */
				double lx = max(bins[binId].lx, ptrckt.nodes[i].x_coord);
				double hx = min(bins[binId].hx, ptrckt.nodes[i].x_coord + ptrckt.nodes[i].width);
				double ly = max(bins[binId].ly, ptrckt.nodes[i].y_coord);
				double hy = min(bins[binId].hy, ptrckt.nodes[i].y_coord + ptrckt.nodes[i].height);

				if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
				{
					double common_area = (hx-lx) * (hy-ly);
					if(ptrckt.nodes[i].isFixed)
						bins[binId].f_util += common_area;
					else 
						bins[binId].m_util += common_area;
				}
			}
	}

	/* (b) non-rectangular fixed shapes */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
		for(unsigned m = 0; m < ptrckt.nodes[i].shapeIds.size(); m++) // Skip normal nodes because m = 0
		{    
			// Divide non-regular fixed shapes into rectangles and use tha above method to calculate areas
			unsigned s = ptrckt.nodes[i].shapeIds[m];
			int lcol = max((int)floor((ptrckt.shapes[s].x_coord - ptrckt.lx)/gridUnit), 0);
			int rcol = min((int)floor((ptrckt.shapes[s].x_coord + ptrckt.shapes[s].width - ptrckt.lx)/gridUnit), x_gridNum-1);
			int brow = max((int)floor((ptrckt.shapes[s].y_coord - ptrckt.by)/gridUnit), 0);
			int trow = min((int)floor((ptrckt.shapes[s].y_coord + ptrckt.shapes[s].height - ptrckt.by)/gridUnit), y_gridNum-1);

			for(int j=brow;j<=trow;j++)
				for(int k=lcol;k<=rcol;k++)
				{
					unsigned binId= j*x_gridNum+k;

					/* get intersection */
					double lx=max(bins[binId].lx, ptrckt.shapes[s].x_coord);
					double hx=min(bins[binId].hx, ptrckt.shapes[s].x_coord + ptrckt.shapes[s].width);
					double ly=max(bins[binId].ly, ptrckt.shapes[s].y_coord);
					double hy=min(bins[binId].hy, ptrckt.shapes[s].y_coord + ptrckt.shapes[s].height);

					if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
					{
						double common_area = (hx - lx) * (hy - ly);
						bins[binId].f_util += common_area;
					}
				}
			}

	/* (c) row blockages */
	for(unsigned i = 0; i < ptrckt.blks.size(); i++)
	{
		int lcol = max((int)floor((ptrckt.blks[i].x_coord - ptrckt.lx)/gridUnit), 0);
		int rcol = min((int)floor((ptrckt.blks[i].x_coord + ptrckt.blks[i].width - ptrckt.lx)/gridUnit), x_gridNum-1);
		int brow = max((int)floor((ptrckt.blks[i].y_coord - ptrckt.by)/gridUnit), 0);
		int trow = min((int)floor((ptrckt.blks[i].y_coord + ptrckt.blks[i].height - ptrckt.by)/gridUnit), y_gridNum-1);

		for(int j = brow; j <= trow; j++)
			for(int k = lcol; k <= rcol; k++)
			{
				unsigned binId = j * x_gridNum + k;

				/* get intersection */
				double lx = max(bins[binId].lx, ptrckt.blks[i].x_coord);
				double hx = min(bins[binId].hx, ptrckt.blks[i].x_coord+ptrckt.blks[i].width);
				double ly = max(bins[binId].ly, ptrckt.blks[i].y_coord);
				double hy = min(bins[binId].hy, ptrckt.blks[i].y_coord+ptrckt.blks[i].height);

				if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
				{
					double common_area = (hx-lx) * (hy-ly);
					bins[binId].f_util += common_area;
				}
			}
	}

	/* 2. determine the free space & utilization per bin */
	for(int j = 0; j < y_gridNum; j++)
	{	
		for(int k = 0; k < x_gridNum; k++)
		{
			unsigned binId = j * x_gridNum + k;
			if(bins[binId].area > gridUnit * gridUnit * BIN_AREA_THRESHOLD)
			{
				bins[binId].free_space = bins[binId].area - bins[binId].f_util;
				if(bins[binId].free_space > FREE_SPACE_THRESHOLD * bins[binId].area)
					util_array[binId] = bins[binId].m_util / bins[binId].free_space;
			}
		}
	}
	
	bins.clear();
}

int index_translate(int binId, int row)
{
	return (binId / x_gridNum) * BIN_DIM * x_gridNum + row * x_gridNum + binId % x_gridNum;
}

int minimum_distance_node2row(ckt & ptrckt, node & this_node, tinyRow & dest_row)
{
	int delta_y = abs(this_node.initial_y - dest_row.y);
	int delta_x = min(abs(this_node.initial_x - dest_row.rx), abs(this_node.initial_x - dest_row.lx));
	return delta_x + delta_y;
}

void initialize_net(ckt & ptrckt)
{
	for(unsigned i = 0; i < ptrckt.nets.size(); i++)
	{
		double netMaxX = ptrckt.lx; 
		double netMinX = ptrckt.rx;
		double netMaxY = ptrckt.by; 
		double netMinY = ptrckt.ty;

		net & this_net = ptrckt.nets[i];

		for(unsigned j = 0;j < this_net.nodeIds.size(); j++)
		{
			node & this_node = ptrckt.nodes[ this_net.nodeIds[j] ];
			double x_pinloc = this_node.x_coord + 0.5 * this_node.width + this_net.x_offset[j];
			double y_pinloc = this_node.y_coord + 0.5 * this_node.height + this_net.y_offset[j];
			if(j == 0)
			{
				netMaxX = netMinX = x_pinloc;
				netMaxY = netMinY = y_pinloc;
			}
			else
			{
				netMaxX = max(netMaxX, x_pinloc);
				netMinX = min(netMinX, x_pinloc);
				netMaxY = max(netMaxY, y_pinloc);
				netMinY = min(netMinY, y_pinloc);
			}
		}

		this_net.max_X = netMaxX;
		this_net.min_X = netMinX;
		this_net.max_Y = netMaxY;
		this_net.min_Y = netMinY;
	}
}


/*-----------------------------------------------*/
/*  Desc: A function to output placement result  */
/*-----------------------------------------------*/

void output_placement(ckt & ptrckt, const char * filename)
{
	ofstream outfile;
	outfile.open(filename);
	outfile << "# HappyPKU Solution" << endl << endl;

	vector<node>::iterator it, nodes_end;
	nodes_end = ptrckt.nodes.end();
	for(it = ptrckt.nodes.begin(); it != nodes_end; ++it)
	{
		outfile << it->obj_name << ' ' << it->x_coord << ' ' << it->y_coord << ' ' << ':' << ' ' << 'N' << ' ';
		if(it->isNI)
			outfile << "/FIXED_NI" << endl;
		else if(it->isFixed)
			outfile << "/FIXED" << endl;
		else
			outfile << endl;
	}
	
	outfile.close();

}
